package com.harvey.study.data.structure.datastructure.linkedlist;


/**
 * date: 2021-04-23
 * desc: 双向链表 
 */
public class TwoWayLinkedList<T>  {
    private int length;
    private TwoWayNode<T> node = new TwoWayNode<T>();

    /**
     * 思路找到上一个节点，原因是方便对新增节点的上个节点赋值
     * @param data
     * @param pos
     * @return
     */
    public boolean add(T data,int pos){
        checkPos(pos);
        length++;
        if(pos == 1){
            this.node.data = data;
            return true;
        }
        int index = 1;
        TwoWayNode<T> p = this.node;
        while(index++ < pos-1){
            p = p.next;
        }
        p.next = new TwoWayNode<>(p,data);
        return true;
    }

    public boolean add(T data){
        return add(data,length+1);
    }

    public boolean remove(int pos){
        checkPos(pos);
        TwoWayNode<T> p = findNode(pos);
        if(p.prev == null && p.next == null){
            this.node = new TwoWayNode<>();
        }else if(p.next == null){
            p.prev.next = p.next;
        }else if(p.prev == null){
            p.next.prev = p.prev;
            this.node = p.next;
        }else{
            p.prev.next = p.next;
            p.next.prev = p.prev;
        }
        length--;
        return true;
    }

    public void clear(){
        this.node = new TwoWayNode<>();
        this.length = 0;
    }

    public TwoWayNode<T> findNode(int pos){
        checkPos(pos);
        int index = 1;
        TwoWayNode<T> p = this.node;
        while(index++ < pos){
            p = p.next;
        }
        return p;
    }

    public T findValue(int pos){
        return findNode(pos).data;
    }

    public TwoWayNode<T> findFirstNode(){
        return this.node;
    }

    public TwoWayNode<T> findLastNode(){
        TwoWayNode<T> p = this.node;
        while(node.next != null){
            p = p.next;
        }
        return p;
    }

    public int size(){
        return length;
    }

    public boolean isEmpty(){
        return length == 0;
    }

    private void checkPos(int pos){
        if(pos<1 || pos>length+1){
            throw new RuntimeException("pos不合法");
        }
    }

    public static void main(String[] args) {
        TwoWayLinkedList<String> list = new TwoWayLinkedList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.remove(3);
        list.add("c");


        TwoWayNode<String> twoWay = list.node;
        while(twoWay!=null){
            System.out.println(twoWay.data);
            twoWay = twoWay.next;
        }
    }
    
}
